package com.leetcode.algorithm.y22.m07.w4;

import java.util.ArrayList;
import java.util.List;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 113. 路径总和 II
 * 
 * https://leetcode.cn/problems/path-sum-ii/
 * 
 * @author jie.deng
 *
 */
class Question0113Solution01 {

	public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
		List<List<Integer>> list = new ArrayList<>();
		if (root == null) {
			return list;
		}
		List<Integer> pathList = new ArrayList<>();
		pathSum(root, 1, 0, targetSum, pathList, list);
		return list;
	}

	private void pathSum(TreeNode cur, int level, int pathSum, int targetSum, List<Integer> pathList,
			List<List<Integer>> list) {
		// 递归终止条件
		if (cur.left == null && cur.right == null) {
			pathSum += cur.val;
			if (targetSum == pathSum) {
				if (pathList.size() >= level) {
					pathList.set(level - 1, cur.val);
				} else {
					pathList.add(cur.val);
				}
				list.add(new ArrayList<>(pathList.subList(0, level)));
			}
			return;
		}

		// 当前层
		pathSum += cur.val;
		if (pathList.size() >= level) {
			pathList.set(level - 1, cur.val);
		} else {
			pathList.add(cur.val);
		}

		// 递归调用
		if (cur.left != null) {
			pathSum(cur.left, level + 1, pathSum, targetSum, pathList, list);
		}
		if (cur.right != null) {
			pathSum(cur.right, level + 1, pathSum, targetSum, pathList, list);
		}
	}

}